package com.cg.offer;

import org.junit.Test;

import java.util.Stack;

/**
 * 剑指Offer 33.二叉搜索树的后序遍历序列
 *
 * @program: LeetCode->Offer_33
 * @description: 剑指Offer 33.二叉搜索树的后序遍历序列
 * @author: cg
 * @create: 2022-03-28 22:00
 **/
public class Offer_33 {

    @Test
    public void test33() {
        System.out.println(verifyPostorder(new int[]{1, 6, 3, 2, 5}));
    }

    /**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
     * 参考以下这颗二叉搜索树：
     * 5
     * / \
     * 2   6
     * / \
     * 1   3
     * <p>
     * 示例 1：
     * 输入: [1,6,3,2,5]
     * 输出: false
     * <p>
     * 示例 2：
     * 输入: [1,3,2,6,5]
     * 输出: true
     * <p>
     * 提示：
     * 数组长度 <= 1000
     *
     * @param postorder
     * @return
     */
    public boolean verifyPostorder(int[] postorder) {
        // 递归实现
        return helper(postorder, 0, postorder.length - 1);
    }

    boolean helper(int[] postorder, int left, int right) {
        //如果left==right，就一个节点不需要判断了，如果left>right说明没有节点，
        //也不用再看了,否则就要继续往下判断
        if (left >= right) {
            return true;
        }
        //因为数组中最后一个值postorder[right]是根节点，这里从左往右找出第一个比
        //根节点大的值，他后面的都是根节点的右子节点（包含当前值，不包含最后一个值，
        //因为最后一个是根节点），他前面的都是根节点的左子节点
        int mid = left;
        int root = postorder[right];
        while (postorder[mid] < root) {
            mid++;
        }
        int temp = mid;
        //因为postorder[mid]前面的值都是比根节点root小的，
        //我们还需要确定postorder[mid]后面的值都要比根节点root大，
        //如果后面有比根节点小的直接返回false
        while (temp < right) {
            if (postorder[temp++] < root) {
                return false;
            }
        }
        //然后对左右子节点进行递归调用
        return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
    }

    /*public boolean verifyPostorder(int[] postorder) {
        // 单调栈实现
        Stack<Integer> stack = new Stack<>();
        int parent = Integer.MAX_VALUE;
        //注意for循环是倒叙遍历的
        for (int i = postorder.length - 1; i >= 0; i--) {
            int cur = postorder[i];
            //当如果前节点小于栈顶元素，说明栈顶元素和当前值构成了倒叙，
            //说明当前节点是前面某个节点的左子节点，我们要找到他的父节点
            while (!stack.isEmpty() && stack.peek() > cur) {
                parent = stack.pop();
            }
            //只要遇到了某一个左子节点，才会执行上面的代码，才会更
            //新parent的值，否则parent就是一个非常大的值，也就
            //是说如果一直没有遇到左子节点，那么右子节点可以非常大
            if (cur > parent) {
                return false;
            }
            //入栈
            stack.add(cur);
        }
        return true;
    }*/

}
